#pragma once
#ifndef AVL_CPP
#define AVL_CPP

#include "AVL.h"
#include "IteradorAVL.h"
#include "Iterador.h"

 
template <class T>
AVL<T>::AVL(Puntero<Comparador<T>> comparador)
{
	this->raiz = NULL;
	this->varioH = false;
	this->tamanio = 0;
	this->comparadorClave = comparador;
}

//template <class T>
//AVL<T>::AVL(Comparador<T> comparador)
//{
//	this->raiz = NULL;
//	this->varioH = false;
//	this->tamanio = 0;
//	this->comparadorClave = comparador;
//}

template <class T>
void AVL<T>:: Insertar(const T &x)
{
	this->varioH = false;
	this->insertarEnAVL(x, this->raiz);
}

template <class T>
bool AVL<T>:: EsVacio() const
{
	return this->raiz == NULL;
}

template <class T>
const T& AVL<T>::Raiz() const
{
	return this->raiz->dato;
}

template <class T>
const T& AVL<T>::Maximo() const
{
	return this->obtenerMaximo(this->raiz);
}

template <class T>
const T& AVL<T>::Minimo() const
{
	return this->obtenerMinimo(this->raiz);
}

template <class T>
bool AVL<T>::Existe(const T &x) const
{
	return this->existeDato(x, this->raiz);
}

template <class T>
void AVL<T>::Borrar(const T &x)
{
	this->borrarEnAVL(x, this->raiz);
	this->tamanio--;
}

template <class T>
void AVL<T>::BorrarTodo()
{
	this->BorrarTodoElArbol(this->raiz);
	this->raiz = NULL;
 
}

template <class T>
const T& AVL<T>::Recuperar(const T& x) const
{
	return this->recuperarDato(x, this->raiz);
}

template <class T>
Iterador<T> AVL<T>::ObtenerIterador() const
{
	return new IteradorAVL<T>(this->raiz, this->tamanio);	
}


template <class T>	
Puntero<NodoAVL<T>> AVL<T>::crearNodoAVL(const T &dato){
	Puntero<NodoAVL<T>> nuevo = new NodoAVL<T>();
	nuevo->dato = dato;
	nuevo->fb = 0;
	nuevo->izq = nuevo->der = NULL;
	varioH = true;
	tamanio++;
	return nuevo;
}	

template <class T>
int AVL<T>::Altura(Puntero<NodoAVL<T>> nodo) const
{
    if (nodo == NULL)
        return 0;
    nat alturaI = Altura(nodo->izq);
    nat alturaD = Altura(nodo->der);

    return 1 + (alturaI > alturaD ? alturaI : alturaD);
}

template <class T>
Puntero<NodoAVL<T>> AVL<T>::insertarEnAVL(const T &dato, Puntero<NodoAVL<T>> &nodoAVL)
{
	Puntero<NodoAVL<T>> p1, p2;
	if(nodoAVL == NULL){
		nodoAVL = crearNodoAVL(dato);
	}
	else
		if(comparadorClave->EsMenor(dato,nodoAVL->dato)){
		//if(d < nodoAVL->dato){
			nodoAVL->izq = insertarEnAVL(dato,nodoAVL->izq);
			if (varioH)  // crecio altura de subarbol izquierdo
				switch(nodoAVL->fb){
					case 1:
						nodoAVL->fb = 0;
						varioH = false;
						break;
					case 0:
						nodoAVL->fb= -1;
						break;
					case -1:
						p1 = nodoAVL->izq;
						if(p1->fb == -1){	// rotacion II simple
							rotacionSimpleIzq(nodoAVL);
						}
						else{	// rotacion ID doble
							rotacionDobleIzq(nodoAVL);
						}

						nodoAVL->fb = 0;
						varioH= false;
			}
		}
		else
			if(comparadorClave->EsMayor(dato,nodoAVL->dato)){
			//if (d > nodoAVL->dato) { // alta en subarbol der: mayores
				nodoAVL->der = insertarEnAVL(dato,nodoAVL->der);
				if(varioH)	// crecio la altura subarbol derecho
					switch (nodoAVL->fb){
						case -1:
							nodoAVL->fb = 0;
							varioH = false;
							break;
						case 0:
							nodoAVL->fb = 1;
							break;
						case 1:
							p1=nodoAVL->der;
							if(p1->fb == 1){	// rotacion DD simple
								rotacionSimpleDer(nodoAVL);
							}
							else {	// rotacion DI doble 
								rotacionDobleDer(nodoAVL);							
							}
							nodoAVL->fb=0;
							varioH=false;
				}
			}

			else // ya esta en el arbol
				varioH = false;
	return nodoAVL;
 

}


template <class T>
const T& AVL<T>::obtenerMaximo(const Puntero<NodoAVL<T>> &nodo) const{
	if (nodo->der == NULL){
		return nodo->dato;
	}
	else{
		return obtenerMaximo(nodo->der);
	}
}

template <class T>
const T& AVL<T>::obtenerMinimo(const Puntero<NodoAVL<T>> &nodo) const{
	if (nodo->izq == NULL){
		return nodo->dato;
	}
	else{
		return obtenerMinimo(nodo->izq);
	}
}

template <class T>
bool AVL<T>::existeDato(const T &dato, const Puntero<NodoAVL<T>> &nodo) const{
	if (nodo == NULL){
		return false;
	}
	else if (comparadorClave->SonIguales(dato, nodo->dato)){
		return true;
	}
	else if (comparadorClave->EsMenor(dato, nodo->dato)){
		return existeDato(dato, nodo->izq);
	}
	else{
		return existeDato(dato, nodo->der);	
	}
}


template <class T>
const T& AVL<T>::recuperarDato(const T &dato, const Puntero<NodoAVL<T>> &nodo) const{
	if (comparadorClave->SonIguales(dato, nodo->dato)){
		return nodo->dato;
	}
	else if (comparadorClave->EsMenor(dato, nodo->dato)){
		return recuperarDato(dato, nodo->izq);
	}
	else{
		return recuperarDato(dato, nodo->der);			
	}
}
	
template <class T>	
bool AVL<T>::borrarEnAVL(const T &dato, Puntero<NodoAVL<T>> &nodo){
	if(nodo != NULL){
		if(this->comparadorClave->EsMenor(nodo->dato, dato)){
			borrarEnAVL(dato, nodo->der);
			if(varioH){
				Puntero<NodoAVL<T>> p1, p2;
				int b1;
				switch(nodo->fb)	{
					case 1:
						nodo->fb = 0;
						break;
					case 0:
						nodo->fb = -1;
						varioH = false;
						break;
					case -1:
						p1 = nodo->izq;
						if(p1 == NULL)	{
							b1=0;
						}
						else	{
							b1 = p1->fb;
							if(b1 != 1)	{
								rotacionSimpleIzq(nodo);
								if(b1 == 0)	{
									nodo->fb = 1;
								}
							}
							else {	
								rotacionDobleIzq(nodo);
							}
						}
					varioH = true;
				}
			}
		}
		else if (this->comparadorClave->EsMayor(nodo->dato,dato))	{
			borrarEnAVL(dato,nodo->izq);
			if (varioH)	{
				Puntero<NodoAVL<T>>  p1, p2;
				int d1;
				switch(nodo->fb){
				case -1:
					nodo->fb = 0;
					break;
				case 0:
					nodo->fb = 1;
					varioH = false;
					break;
				case 1:
					p1 = nodo->der;

					if(p1 == NULL)	{
						d1 = 0;
					}
					else	{
						d1 = p1->fb;
						if(d1 != -1) {	
							rotacionSimpleDer(nodo);
							if(d1 == 0)	{
								nodo->fb = -1;
							}
						}
						else{	
							rotacionDobleDer(nodo);
						}
					}
					varioH=true;
				}
			}
		}
		else {
			if (nodo->der != NULL && nodo->izq != NULL) {
				T pred = obtenerMaximo(nodo->izq);
				nodo->dato = pred;
				borrarEnAVL(pred, nodo->izq);
				if (varioH){
					Puntero<NodoAVL<T>>  p1, p2;
					int b1;
					switch(nodo->fb){
						case 0:
							nodo->fb=-1;
							varioH=false;
							break;
						case 1:
							nodo->fb=0;
							break;
						case -1:
						p1 = nodo->izq;
						b1 = p1->fb;

						if(b1 != 1){	
							rotacionSimpleIzq(nodo);
						}
						else {	
							rotacionDobleIzq(nodo);
						}
					varioH=true;
					}
				}
			}
			else {
				Puntero<NodoAVL<T> > temp = nodo;
				if (nodo->der == NULL){
					nodo = nodo->izq;
				}
				else	{
					nodo = nodo->der;
				}
				temp=NULL;
				varioH = true;
			}	
		}
	}
	return true;
}
 
template <class T>	
void AVL<T>::rotacionSimpleDer(Puntero<NodoAVL<T>> &nodo)
{
	Puntero<NodoAVL<T>> A = nodo;
	Puntero<NodoAVL<T>> B = A->der;
	Puntero<NodoAVL<T>> F = B->izq;

	B->izq = A;
	A->der = F;

	A->fb = 0;
	B->fb = 0;

	nodo = B;
}

template <class T>	
void AVL<T>::rotacionSimpleIzq(Puntero<NodoAVL<T>> &nodo)
{
	Puntero<NodoAVL<T>> A = nodo;
	Puntero<NodoAVL<T>> B = A->izq;
	Puntero<NodoAVL<T>> F = B->der;

	B->der = A;
	A->izq = F;

	A->fb = 0;
	B->fb = 0;

	nodo = B;
}

template <class T>	
void AVL<T>::rotacionDobleDer(Puntero<NodoAVL<T>> &nodo)
{
	Puntero<NodoAVL<T>> pa = nodo;
	Puntero<NodoAVL<T>> p1 = pa->der;
	Puntero<NodoAVL<T>> p2 = p1->izq;

	p1->izq = p2->der;
	p2->der = p1;

	pa->der = p2->izq;
	p2->izq = pa;

	pa->fb = p2->fb ==  1 ? -1 : 0;
	p1->fb = p2->fb == -1 ?  1 : 0;
	
	nodo = p2;
}
	
template <class T>	
void AVL<T>::rotacionDobleIzq(Puntero<NodoAVL<T>> &nodo)
{
	Puntero<NodoAVL<T>> pa = nodo;
	Puntero<NodoAVL<T>> p1 = pa->izq;
	Puntero<NodoAVL<T>> p2 = p1->der;
	
	p1->der = p2->izq;
	p2->izq = p1;

	pa->izq = p2->der;
	p2->der = pa;

	pa->fb = p2->fb == -1 ?  1 : 0;
	p1->fb = p2->fb ==  1 ? -1 : 0;

	nodo = p2;
}

template <class T>	
void AVL<T>::BorrarTodoElArbol(Puntero<NodoAVL<T>> &nodo)
{
	if(nodo!= NULL){
		BorrarTodoElArbol(nodo->izq);
		BorrarTodoElArbol(nodo->der);
	     
		nodo = NULL;
	}
}

#endif
